1. Field of the Invention
The present invention relates to circuitry for computer systems, and more specifically, to microprocessor shifter circuits utilizing butterfly and inverse butterfly circuits, and control circuits therefor.
2. Related Art
Bit manipulation operations are important features of modern microprocessors. Unfortunately, bit manipulation operations carried out by existing microprocessors are limited in terms of flexibility and ease of implementation at the hardware level. For example, bit manipulation operations performed by existing microprocessors are often limited to shift and rotate operations. Since a microprocessor is typically optimized around the processing of words (i.e., fixed-length groups of binary bits of information), it is not surprising that bit-level operations are not well-supported by current word-oriented microprocessors. Simple “bit-parallel” Boolean operations such as AND, OR, XOR, and NOT are usually supported as the “logical” operations of the Arithmetic-Logic Unit (ALU), the most fundamental functional unit of a microprocessor. However, only very simple non-bit-parallel operations are supported, such as shift and rotate operations, in which all bits of an operand move by the same amount. These operations are usually supported by separate shifter functional units.
A few microprocessor Instruction Set Architectures (ISAs) have more advanced bit operations. However, these operations are implemented by complex shifter functional unit circuitry, which appreciably adds to the size and complexity of the microprocessor. Examples of such operations include subword extract and deposit operations (e.g., “pextrw” and “pinsrw” operations in the INTEL IA-32 ISA), field extract and deposit operations (e.g., “extr” and “dep” operations in HEWLETT PACKARD PA-RISC or INTEL IA-64 ISAs), or rotate and mask operations (e.g., “rldimi” in POWERPC ISA). These can be viewed as variants of the basic shift or rotate operation operations, with certain bits masked out and set to zeros, or sign bits replicated, or bits from a second operand merged into the result. Additionally, some instruction sets have multimedia permute operations that rearrange the subwords packed into one or more registers (e.g., “mix” operation in HEWLETT PACKARD PA-RISC 2.0 and INTEL IA-64 architectures).
There are also many emerging applications, such as cryptography, imaging, and bioinformatics, where even more advanced bit manipulation operations are needed. While circuitry to achieve these operations can be built by assembling simple logical and shift operation circuits, or by implementing same in firmware, such approaches often result in very large circuits or slow execution speeds. Applications using these advanced bit manipulation operations would thus be significantly sped-up if the processor were able to support more powerful bit manipulation instructions. Such operations include arbitrary bit permutations, bit gather operations (performing multiple bit-field extract operations in parallel), and bit scatter operations (performing multiple bit-field deposit operations in parallel).
Accordingly, what would be desirable, but has not yet been provided, are shifter circuits utilizing butterfly and inverse butterfly circuits, and control circuits therefor, which address the foregoing shortcomings of existing microprocessors.